// https://www.lintcode.com/problem/prime-number-of-set-bits-in-binary-representation/

public class Solution {
    /**
     * @param L: an integer
     * @param R: an integer
     * @return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation
     */
    public int countPrimeSetBits(int L, int R) {
    	int ret = 0;
    	for (int i = L; i <= R; ++i) {
    	    int c = countOne(i);
    	    if (isPrime(c)) {
    	        ++ret;
    	    }
    	}
    	return ret;
	}
	
	protected int countOne(int n) {
	    int ret = 0;
	    while (n > 0) {
	        if ((n % 2) == 1) {
	            ++ret;
	        }
	        n /= 2;
	    }
	    return ret;
	}
	
	protected boolean isPrime(int n) {
	    if (n == 1) {
	        return false;
	    } else if (n == 2) {
	        return true;
	    } else {
	        for (int i = 2; i < n; ++i) {
	            if ((i * i) <= n) {
	                if ((n % i) == 0) {
	                    return false;
	                }
	            } else {
	                break;
	            }
	        }
	        return true;
	    }
	}
}